home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_02 / otto / bzyatg.c < prev    next >
C/C++ Source or Header  |  1993-12-01  |  6KB  |  278 lines
  1. /*********************************************
  2.  *
  3.  * Fast String Search, using shift or algorithm
  4.  *
  5.  * July 1993 by Erick Otto.
  6.  *
  7.  * Algorithms from Beaza-Yates and Gonnet
  8.  * are used in this code.
  9.  * 
  10.  *********************************************/
  11.  
  12. #include    <stdio.h>
  13. #include    <fcntl.h>
  14. #include    <ctype.h>
  15.  
  16. #define WORD    32   /* # of bits in an Uint */
  17. #define B        1   /* # of bits to shift   */
  18. #define MAXSYM 256   /* alphabet size        */
  19.  
  20. unsigned int stopmask;
  21. unsigned int T[MAXSYM];
  22.  
  23. #define TBUF (8*BUFSIZ) /* X times system buffer */
  24.  
  25. #define MAXPAT WORD
  26.  
  27. main(argc, argv)
  28. int argc;
  29. char **argv;
  30. {
  31.     char buf[TBUF+2];
  32.     char match[MAXPAT];
  33.     register int fd, nread;
  34.     register char *beg, *lastnl, *end;
  35.     char filename[100];
  36.     char first;
  37.     char build();
  38.  
  39.     /* must be at least two arguments */
  40.     if (argc < 2 ) {
  41.         fprintf(stderr,"\n\tMatch string expected\n");
  42.         exit(1);
  43.     }
  44.     if (argc < 3 ) {
  45.         fprintf(stderr,"\n\tFile expected\n");
  46.         exit(1);
  47.     }
  48.  
  49.     strcpy(match, argv[1]);
  50.     strcpy(filename, argv[2]);
  51.     first = build(match);
  52.  
  53.     if ( (fd = open(filename,O_RDONLY)) == -1) {
  54.         fprintf(stderr,
  55.            "Can't open file %s\n",filename);
  56.             perror(filename);
  57.             exit(1);
  58.     }
  59.  
  60.     *buf = '\n';  /* sentinel for printing purposes */
  61.     beg = buf+1;  /* start filling buffer at buf+1  */
  62.  
  63.     while((nread=read(fd,beg,(&buf[TBUF]-beg))) > 0){
  64.         end = beg+nread;
  65.         lastnl = end;
  66.  
  67.         while(*--lastnl != '\n')
  68.             ;
  69.  
  70.         /* lastnl points to the newline */
  71.         matchpat(buf+1, lastnl-buf,first);
  72.  
  73.         /* move the part skipped (from newline  */
  74.     /* to end of buffer) back to the begin  */
  75.     /* of the buffer.                       */
  76.         memcpy(buf+1, lastnl, end-lastnl-1);
  77.         beg = buf+1 + (end-lastnl);
  78.     }
  79.     close(fd);
  80. }
  81.  
  82. char
  83. build(pat)
  84. register char *pat;
  85. {
  86.     unsigned int mask;
  87.     int i,j;
  88.     char *C_pat;
  89.     char *space;
  90.     char *malloc();
  91.     char startrange;
  92.     char endrange;
  93.     char first;
  94.  
  95.     first = *pat;
  96.  
  97.     /* pre process */
  98.  
  99.     if (first == '.' || first == '[') {
  100.         fprintf(stderr,"%s %s\n",
  101.            "Can not start with wildcard \'.\'",
  102.            "or regular expression range");
  103.             exit(1);
  104.     }
  105.  
  106.     /* Initialize the table */
  107.     for (i=0;i<MAXSYM;i++) {
  108.         T[i] = ~0;
  109.     }
  110.  
  111.     /* allow for . wildcard */
  112.     space=malloc((strlen(pat)+1) * sizeof(char));
  113.     if (space == NULL) {
  114.         fprintf(stderr,"Malloc failed\n");
  115.         exit(1);
  116.     }
  117.     C_pat = space;
  118.     mask = ~0;
  119.  
  120.     /* scan the pattern for ranges and or wildcards */
  121.     for(i=1;*pat;i <<= B) {
  122.  
  123.         switch(*pat) {
  124.         
  125.         case '[':
  126.           /*start of a range*/
  127.  
  128.           pat++;
  129.           while(*pat != ']' && *pat) {
  130.  
  131.             if (isalnum(*pat)) {
  132.  
  133.                /* if nxt char is a dash */
  134.                /* it's a range          */
  135.  
  136.                if (*(pat+1) == '-') {
  137.                    startrange = *pat;
  138.                    pat++;
  139.                    pat++;
  140.                    endrange = *pat;
  141.                    for(j=startrange;j<=endrange;j++){
  142.                         T[j] &= ~i;
  143.                    }
  144.                    *C_pat = startrange;
  145.                } else {
  146.                    /*normal character in range*/
  147.                    *C_pat = *pat;
  148.                    T[*pat] &= ~i;
  149.                }
  150.             } else if (*pat == '-') {
  151.  
  152.                if (*(pat-1) == '[') 
  153.                    fprintf(stderr,
  154.               "Invalid Expression\n");
  155.                       exit(1);
  156.                } else {
  157.  
  158.                    fprintf(stderr,
  159.                       "Invalid Expression\n");
  160.                       exit(1);
  161.                }
  162.  
  163.                pat++;
  164.             } /* while not ']' */
  165.             C_pat++;
  166.             break;
  167.  
  168.         case '.': 
  169.           /* We need to set the char position to
  170.            * something special, in this case it doesn't
  171.            * really matter
  172.            */
  173.            *C_pat++ = 'a';
  174.            mask &=~i;
  175.            break;
  176.  
  177.         default:
  178.           *C_pat++ = *pat;
  179.           break;
  180.         } /* end of switch */
  181.         pat++;
  182.     } /* end of for loop */
  183.  
  184.     /* close the string and rewind the ptr */
  185.     *C_pat = '\0';
  186.     C_pat = space;
  187.  
  188.     if (strlen(C_pat) > MAXPAT) {
  189.         fprintf(stderr,
  190.            "Pattern too long max %d chars\n",WORD);
  191.            exit(1);
  192.     }
  193.  
  194.     /* apply wildcard mask to all elements */
  195.     for (i=0;i<MAXSYM;i++) {
  196.         T[i] = T[i] & mask;
  197.     }
  198.  
  199.     /* Set masks for all chars that occur */
  200.     /* in the pattern and calculate the   */
  201.     /* match criteria                     */
  202.  
  203.     stopmask=0;
  204.     for(j=1;*C_pat;j <<=B) {
  205.         T[*C_pat] &= ~j;
  206.         stopmask |=j;
  207.         C_pat++;
  208.     }
  209.  
  210.     stopmask = ~(stopmask >>B);
  211.     free(space);
  212.     return(first);
  213. }
  214.  
  215. matchpat(text,n,first)
  216. register char *text;
  217. int n;
  218. char first;
  219. {
  220.  
  221.     register unsigned int state,initial;
  222.     int matches;
  223.     int gotoeol = 0;
  224.     register char *nl;
  225.     register char *end;
  226.     char *savepos;
  227.     char savechar;
  228.  
  229.     end = text+n;
  230.  
  231.     /* save the last character    */
  232.     /* which we use as a sentinel */
  233.     /* for the while loop         */
  234.     savepos  = end+1;
  235.     savechar = *savepos;
  236.     *savepos = first;
  237.  
  238.     /* search */
  239.     matches = 0;
  240.     initial = ~0;
  241.  
  242.     do {
  243.  
  244.         /* fast scan */
  245.         while(*text != first) text++;
  246.  
  247.         if (text > end) continue;
  248.  
  249.         state=initial;
  250.  
  251.         do {
  252.  
  253.             state= (state << B) | T[*text];
  254.  
  255.             if (state <stopmask) {
  256.                /****** match **********/
  257.  
  258.                nl=text;    
  259.  
  260.                /*look back for the closest newline*/
  261.                while(*--nl != '\n')
  262.                    ;
  263.  
  264.                while(*++nl != '\n') putchar(*nl);
  265.                putchar('\n');
  266.  
  267.                /* skip the rest of the line */
  268.                text=nl;
  269.             }
  270.             text++;
  271.         } while ( state != initial);
  272.     } while (text < end);
  273.  
  274.     /* reset the character saved */
  275.     *savepos=savechar;
  276.     return(0);
  277. }
  278.